#pragma once
#ifndef _BESTFIRSTSEARCH_H_
#define _BESTFIRSTSEARCH_H_

#include <memory>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map> //tr1


template <class State, class Heuristic, class Successors>
class BestFirstSearch
{  
  public:
	typedef std::vector<State> SuccessorCollection;

	class Node
	{
	  public:
		const State state;
		unsigned int h;
		Node *parent;

		Node( const State &s ) : state(s), h(0), parent(NULL) {}
		Node( const State &s, unsigned int h_, Node *parent_ ) : state(s), h(h_), parent(parent_) {}
	};



  protected:
	struct NodeHueristicLessThan {
		bool operator()( const Node *n1, const Node *n2 ) const
		{ return n1->h > n2->h; }
	};
	
	typedef std::vector<Node *> OpenCollection;
	typedef std::tr1::unordered_map<State, Node *> OpenHashMap;
	typedef std::map<State, Node *> ClosedCollection;
	NodeHueristicLessThan m_HueristicComparer;

  private:	
	std::allocator<Node> m_Allocator;
	OpenCollection m_OpenList; 
	OpenHashMap m_OpenHashMap;
	ClosedCollection m_ClosedList;
	Heuristic m_HeuristicFunction;
	Successors m_SuccessorsOf;
	Node *m_pNodePath;

#ifdef _BESTFIRSTSEARCH_MEMORY_DEBUG
	int nAllocations;
#endif

  public:
	BestFirstSearch( );
	~BestFirstSearch( );


	bool find( const State &start, const State &end );
	Node *getPath( );
	void cleanup( );

  protected:
	Node *openListBestCandidate( );
	void openListPush( Node *&t );
	void openListPop( );
	void openListHeapify( );
	Node *openListFind( State s );
};

template <class State, class Heuristic, class Successors>
inline typename BestFirstSearch<State, Heuristic, Successors>::Node *BestFirstSearch<State, Heuristic, Successors>::getPath( )
{ return m_pNodePath; }


template <class State, class Heuristic, class Successors>
inline typename BestFirstSearch<State, Heuristic, Successors>::Node *BestFirstSearch<State, Heuristic, Successors>::openListBestCandidate( )
{ return m_OpenList.front( ); }


template <class State, class Heuristic, class Successors>
inline void BestFirstSearch<State, Heuristic, Successors>::openListPush( Node *&t )
{
	m_OpenList.push_back( t );
	push_heap( m_OpenList.begin( ), m_OpenList.end( ), m_HueristicComparer );

	m_OpenHashMap[ t->state ] = t; 
}

template <class State, class Heuristic, class Successors>
inline void BestFirstSearch<State, Heuristic, Successors>::openListPop( )
{
	Node *pNode = m_OpenList.front( );
	pop_heap( m_OpenList.begin( ), m_OpenList.end( ), m_HueristicComparer );
	m_OpenList.pop_back( );

	m_OpenHashMap.erase( pNode->state );
}

template <class State, class Heuristic, class Successors>
inline void BestFirstSearch<State, Heuristic, Successors>::openListHeapify( )
{ std::make_heap( m_OpenList.begin( ), m_OpenList.end( ), m_HueristicComparer ); }



template <class State, class Heuristic, class Successors>
inline typename BestFirstSearch<State, Heuristic, Successors>::Node *BestFirstSearch<State, Heuristic, Successors>::openListFind( State s )
{
	OpenHashMap::iterator itr = m_OpenHashMap.find( s );

	if( itr == m_OpenHashMap.end( ) )
	{
		return NULL;
	}
	else
	{
		return itr->second;
	}
}

#include "BestFirstSearch.inl"
#endif